The present invention relates to keyword search systems, and more specifically, to dynamic authority-based keyword search systems.
A variety of algorithms are in use for keyword searches in databases and on the Internet. Dynamic, authority-based search algorithms, leverage semantic link information to provide high quality, high recall search results. For example, the PageRank algorithm utilizes the Web graph link structure to assign global importance to Web pages. It works by modeling the behavior of a “random web surfer” who starts at a random web page and follows outgoing links with uniform probability. The PageRank score is independent of a keyword query. Recently, dynamic versions of the PageRank algorithm have been developed. They are characterized by a query-specific choice of the random walk starting points. Two examples are Personalized PageRank for Web graph datasets and ObjectRank for graph-modeled databases.
Personalized Page Rank is a modification of PageRank that performs search personalized on a preference set that contains web pages that a user likes. For a given preference set, PPR performs an expensive fixpoint iterative computation over the entire Web graph, while it generates personalized search results.
ObjectRank extends Personalized PageRank to perform keyword search in databases. ObjectRank uses a query term posting list as a set of random walk starting points, and conducts the walk on the instance graph of the database. The resulting system is well suited for “high recall” search, which exploits different semantic connection paths between objects in highly heterogeneous datasets. ObjectRank has successfully been applied to databases that have social networking components, such as bibliographic data and collaborative product design.